import java.util.HashMap;
import java.util.Map;

public class Main {
    static class Node{
        int value;
        Node prev;
        Node next;
        public Node(int value){
            this.value = value;
        }
    }
    int num;
    Node head = new Node(-1);
    Map<Integer,Node> map = new HashMap<>();
    public Main(int num){
        this.num = num;
        head.prev = head;
        head.next = head;
    }
    public void put(int key, int value){
        Node node = map.get(key);
        if(node != null){
            map.get(key).value = value;
            return;
        }
        Node newNode = new Node(value);
        map.put(key,newNode);
        newNode.next = head.next;
        newNode.prev = head;
        head.next.prev = newNode;
        head.next = newNode;
        if(map.size()>num){
            Node tail = head.prev;
            map.remove(tail.value);
            tail.prev.next = tail.next;
            tail.next.prev = tail.prev;
        }
    }
    public int get(int x){
        if(map.containsKey(x)){
            Node node = map.get(x);
            node.prev.next = node.next;
            node.next.prev = node.prev;
            node.next = head.next;
            node.prev = head;
            head.next.prev = node;
            head.next = node;
            return node.value;
        }
        return -1;
    }

}
